1. Field of the Invention
The present invention relates generally to communication systems, and, in particular, to decoding systems interleaving/de-interleaving data stored in memory.
2. Description of the Related Art
Many digital transmission systems commonly employ techniques for detection of digital data represented by a sequence of symbols. The symbol bits are transferred as a signal through a transmission (e.g., magnetic/optical storage or other communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered to take place via a transmission channel that has an associated frequency response. Similarly, wired, optical, wireless, and cellular communication systems also transfer encoded data through a channel, which encoded data is then detected and decoded by a receiver. The signal may be read from the channel as a sampled signal (i.e., a sequence of sample values) representing the transmitted encoded data. For processing convenience, the encoding and decoding process is applied to blocks of data, each block representing a portion of the original data sequence.
A characteristic of some communication channels is the addition of “bursty” noise. Such noise may corrupt a transmitted signal for a period of time equivalent to the period of several transmitted symbols (either data or encoded data). The presence of bursty noise may cause burst errors in the received data which subsequently results in an increase Bit-Error Rate (BER) in the frame for any detection system employed to recover the data. Burst errors are typically difficult to recover by a partial response (PR) channel detector in an iterative decoding system, since the burst errors happen in a concentrated manner. To minimize the effect of burst errors, many magnetic storage or communication systems include an interleaver in the transmitter and a corresponding de-interleaver in the receiver. Interleaving is a mapping f(*) that generally comprises receiving a block of data having BLK values (i.e., BLK is the block length and BLK is an integer greater than one), and rearranging the order of the BLK values in the block. Interleaving may also be employed, for example, to remove non-random sequences of values in a data stream. By interleaving the symbols in a block of data prior to transmission through the channel, the de-interleaving process distributes the burst errors throughout the de-interleaved block.
In the data recording industry, an ongoing effort focuses on increasing the amount of information that can be stored and retrieved in various storage media. Unfortunately, increasing the recording density on a given medium (e.g., magnetic or optical) also causes a decrease in the Signal-to-Noise Ratio (SNR) of any data resident on the medium, which subsequently results in an increase Bit-Error Rate (BER) for any detection system employed to recover such resident data.
The performance of digital storage and communication systems with respect to degradation in SNR can be significantly improved by the use of any number of error correction code schemes. As a result, most, if not all, recording and communication systems use some form of error correction coding, which generally involves systematically adding redundant information to a stream of data to insure that individual bit errors generated during a particular write/read/transmission operation can be detected and corrected. In recent years, iterative correction codes have increasingly replaced the more traditionally used block and convolutional correction codes. Iterative codes, such as turbo codes and low-density parity-check (LDPC) codes, have shown very good performance for magnetic storage systems.
Low Density Parity Check (LDPC) codes are a class of linear block codes which provide a near capacity performance on a large collection of data transmission and storage channels. LDPC codes are well known in the art or communications and information theory, and were first proposed by Gallager in his 1960 doctoral dissertation (R. Gallager: “Low-density Parity Check Codes,” IRE transformation series pp 21-28, January 1962). LPDC codes allow for methods of error detection and correction able to achieve near Shannon-limit channel communication. Generally, these methods include iterative decoding techniques that, when applied to sparse parity-check matrices, are capable of achieving a significant fraction of available channel capacity with relatively low complexity. LDPC codes are defined using sparse parity check matrices comprising a small number of non-zero entries.
Since LDPC codes are constructed by juxtaposing smaller circulant (or cyclic) submatices to form the larger parity check or base matrix, iterative decoders also use interleaving and de-interleaving techniques to generate a circulant for processing of read data. A circulant is a square binary matrix where each row is cyclic N-value shift of the row above it, where N is an integer greater than or equal to 1 (the end bit of a row being wrapped around to the beginning of the next row down). In these cases, interleaving is a mapping f(*) that generally comprises receiving a series of data samples representing both user data and parity check data read from, for example, a disk sector. User data bits and parity bits are generally interleaved separately, and LDPC parity bits are distributed through the user data in accordance with the LDPC code construction. This type of interleaving generally creates a 2-dimensional matrix (memory) of values, where the interleaving is defined for row-column ordering prior to applying the matrix to the LDPC decoder.
In order to decode a sequence of data samples read from, for example, a magnetic hard drive, an LDPC decoder requires an associated memory to collect and store a matrix of samples. Multi-way interleaving might be used to partition the associated memory. Multi-way interleaving, given two (or multiple) input LDPC sample matrices, might interleave rows of the two (or multiple) input matrices together in the memory to make efficient use of reading and writing data during the clock cycles, and to spread the burst errors into two (or multiple) component code words.